package com.gitee.ywj1352.算法.week06;


import java.util.HashMap;

public class LRU2 {
    private HashMap<Integer, Node> hashMap;
    private DoubleList doubleList;
    private int maxSize;

    public LRU2(int maxSize) {
        this.hashMap = new HashMap<>();
        this.doubleList = new DoubleList();
        this.maxSize = maxSize;
    }

    private void remove2First(Node node) {
        this.doubleList.remove(node);
        this.doubleList.addLast(node);
    }

    private void makeRen(Node node) {
        this.doubleList.remove(node);
        this.doubleList.addLast(node);
        this.hashMap.put(node.key, node);
    }

    private void removeLast() {
        Node removeFirst = this.doubleList.removeFirst();
        this.hashMap.remove(removeFirst.key);
    }

    public void put(int key, int val) {
        Node node = new Node(key, val);
        if (this.hashMap.containsKey(key)) {
            makeRen(node);
            return;
        }
        // 删除 最近的
        if (this.doubleList.size >= maxSize) {
            this.removeLast();
        }
        this.doubleList.addLast(node);
        this.hashMap.put(key, node);
    }

    public Node get(int key) {
        Node node = hashMap.get(key);
        if (node == null) {
            return null;
        }
        this.remove2First(node);
        return node;
    }

    class DoubleList {
        public Node head, tail;
        public int size;
        public DoubleList() {
            //引入 虚拟节点
            this.head = new Node(0, 0);
            this.tail = new Node(0, 0);
            this.size = 0;
        }

        public void addLast(Node node) {
            node.preNode = tail.preNode;
            tail.preNode.nextNode = node;
            node.nextNode = tail;
            tail.preNode = node;
            size++;
        }

        public Node removeFirst() {
            if (size == 0) return null;
            Node headNode = head.nextNode;
            remove(headNode);
            size--;
            return headNode;
        }

        public void remove(Node node) {
            node.preNode.nextNode = node.nextNode;
            node.nextNode.preNode = node.preNode;
            size--;
        }
    }

    class Node {
        public int val;
        public int key;
        public Node preNode;
        public Node nextNode;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    class Node2 {
        int key;
        int val;
        private Node2 next;
        private Node2 pre;

        public Node2(int key , int val)
        {
            this.key = key;
            this.val = val;
        }
    }
    class DList{
        private Node2 head;
        private Node2 tail;
        private int size;

        public DList(){
            this.head = new Node2(0,0);
            this.tail = new Node2(0,0);
            size = 0;
        }

        public void addFirst(Node2 node){
            node.next = head.next;
            node.pre = head;
            head.next.pre = node;
            head.next = node;
            size ++;
        }

        public Node2 removeLast(){
            if (size == 0 )return null;
            Node2 rN = this.tail.pre;
            remove(rN);
            return rN;
        }


        public void remove(Node2 node){
            Node2 nN = node.next;
            node.pre.next  = nN;
            nN.pre = node.pre;
            size --;
        }

    }
}
